package com.gxc.tree;

/**
 * 双向链表节点结构和二叉树节点结构是一样的，如果你把last认为是left,next认为是next的话。
 * 给定一个搜索二叉树的头节点head，请转化成一条有序的双向链表，并返回链表的头节点。
 *
 * 解法:
 * 二叉树递归，左右子节点构造链表
 * 左子节点构造的链表尾部链接到当前节点的last，
 * 右子节点构造的链表头部链接到当前节点的next，
 * 左子节点构造的链表头作为整个链表的头
 */
public class TreeToLinkedList {

    public TreeNode treeToLinkedList(TreeNode head) {
        if (head == null) return null;
        
        return process(head).start;
    }

    private Info process(TreeNode node) {
        if (node == null) {
            return new Info(null, null);
        }

        Info left = process(node.left);
        Info right = process(node.right);

        if (left.end != null) {
            left.end.right = node;
        }
        if (right.start != null) {
            right.start.left = node;
        }
        node.left = left.end;
        node.right = right.start;
        return new Info(left.start!=null?left.start:node, right.end!=null?right.end:node);
    }

    public class Info {

        public TreeNode start;
        public TreeNode end;

        public Info(TreeNode start, TreeNode end) {
            this.start = start;
            this.end = end;
        }
    }

    public class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;
    }
}
